package com.timous.others;

import com.sun.org.apache.regexp.internal.RE;

/**
 * https://leetcode-cn.com/problems/reverse-words-in-a-string/
 * 输入："the sky is blue"
 * 输出："blue is sky the"
 *
 * 输入："  hello world!  "
 * 输出："world! hello"
 * 解释：输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
 *
 * 输入："a good   example"
 * 输出："example good a"
 * 解释：如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 *
 * 输入：s = "  Bob    Loves  Alice   "
 * 输出："Alice Loves Bob"
 *
 * 输入：s = "Alice does not even like bob"
 * 输出："bob like even not does Alice"
 *
 * 1 <= s.length <= 104
 * s 包含英文大小写字母、数字和空格 ' '
 * s 中 至少存在一个 单词
 *
 * 请尝试使用 O(1) 额外空间复杂度的原地解法。
 *
 * 中间可能有多个字符   中间没有空格是一个单词
 */
public class _151_翻转字符串里的单词 {

    public static void main(String[] args) {
        String s = "are you ok";
        System.out.println(reverseWords(s));
    }

    public static String reverseWords(String s) {
        if (s == null) return null;
        char[] chars = s.toCharArray();
        // 消除多余的空格   直接挪动我们的元素 ， 从前往后
        //字符串最终的有效长度
        int len = 0;
        int cur = 0;
        //前一个字符是不是为空格字符   一开始遇到的字符是空格的话就需要跳过 ，
        // 就需要为true  不然的话  一开始有空格的话就会增加长度 ， 前面的空格是我们不需要的
        boolean space = true;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != ' '){//非空格字符
                chars[cur++] = chars[i];
                space = false;
            }else if (space == false){ //chars[i] 是空格字符   chars[i-1] 是非空格
                chars[cur++] = ' ';
                space = true;
            }
        }
        len = space ? cur-1:cur;
        System.out.println(len);
        //反转操作  写一个函数
        reverseSingleWord(chars , 0 , len);
        cur = 0; //
        for (int i = 0; i < len; i++) {
            if (chars[i] == ' '){
                reverseSingleWord(chars , cur , i);
                cur = i+1;
            }
        }
        reverseSingleWord(chars , cur , len);
        return new String(chars , 0 , len);
    }

    //反转[l , r) 范围内的字符串逆转   也就是把第一个跟最后一个进行交换
    private static void reverseSingleWord(char[] chars , int l , int r){
        r--;
        // l 跟 r进行交换
        while (l < r){
            char temp = chars[l];
            chars[l] = chars[r];
            chars[r] = temp;
            r--;
            l++;
        }
    }
}
